package leetCode.solution;

import java.util.Arrays;

public class Solution1478 {

		public static int minDis1(int[] arr, int num) {
			if (arr == null || arr.length < 2 || num < 1) {
				return 0;
			}
			int n = arr.length;
			int[][] record = getRecord(arr);
			int[][] dp = new int[n][num + 1];

			// 初始化第一列
			for (int i = 0; i < n; i++) {
				dp[i][1] = record[0][i];
			}
			for (int i = 1; i < n; i++) {
				for (int j = 2; j <= Math.min(i, num); j++) {
					dp[i][j] = record[0][i];
					// 0...k...i 中 枚举k...i 放置最后一个邮局的情况
					for (int k = i; k > 0; k--) { // 1 .... i
						dp[i][j] = Math.min(dp[i][j], dp[k - 1][j - 1] + record[k][i]);
					}
				}
			}
			return dp[n - 1][num];
		}
		
		// record[i][j] 放一个邮局的最小距离
		private static int[][] getRecord(int[] arr){
			int n = arr.length;
			int[][] record = new int[n][n];
			for(int i = 0;i<n;i++) {
				for(int j=i+1;j<n;j++) {
					record[i][j]=record[i][j-1]+arr[j]-arr[(j+i)>>1];
				}
			}
			return record;
		}
		
		// 四边形不等式优化dp中的枚举
		public static int minDis2(int[] arr, int num) {
			if (arr == null || arr.length < 2 || num < 1) {
				return 0;
			}
			Arrays.sort(arr);
			int n = arr.length;
			int[][] record = getRecord(arr);
			int[][] dp = new int[n][num + 1];
			int[][] choose = new int[n][num + 1];

			// 初始化第一列
			for (int i = 0; i < n; i++) {
				dp[i][1] = record[0][i];
			}
			for (int i = 1; i < n; i++) {
				for (int j = Math.min(i, num); j >= 2; j--) {
					dp[i][j] = record[0][i];
					// 0...k...i 中 枚举k...i 放置最后一个邮局的情况
					int down = choose[i - 1][j];
					int up = j == Math.min(i, num) ? i : choose[i][j + 1];
					for (int k = Math.min(i, up); k >= Math.max(1, down); k--) {
						if (dp[k - 1][j - 1] + record[k][i] < dp[i][j]) {
							dp[i][j] = dp[k - 1][j - 1] + record[k][i];
							choose[i][j] = k;
						}
					}
				}
			}
			return dp[n - 1][num];
		}
		
		public static int minDistance(int[] houses, int k) {
	        int n = houses.length;
	        Arrays.sort(houses);

	        int[][] medsum = new int[n][n];
	        for (int i = n - 2; i >= 0; --i) {
	            for (int j = i + 1; j < n; ++j) {
	                medsum[i][j] = medsum[i + 1][j - 1] + houses[j] - houses[i];
	            }
	        }

	        int[][] f = new int[n][k + 1];
	        for (int i = 0; i < n; ++i) {
	            Arrays.fill(f[i], Integer.MAX_VALUE / 2);
	        }
	        for (int i = 0; i < n; ++i) {
	            f[i][1] = medsum[0][i];
	            for (int j = 2; j <= k && j <= i + 1; ++j) {
	                for (int i0 = 0; i0 < i; ++i0) {
	                    f[i][j] = Math.min(f[i][j], f[i0][j - 1] + medsum[i0 + 1][i]);
	                }
	            }
	        }

	        return f[n - 1][k];
	    }


		// for test
		public static int[] getSortedArray(int len, int range) {
			int[] arr = new int[len];
			for (int i = 0; i != len; i++) {
				arr[i] = (int) (Math.random() * range);
			}
//			Arrays.sort(arr);
			return arr;
		}

		// for test
		public static void printArray(int[] arr) {
			for (int i = 0; i != arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
		}

		// for test
		public static void main(String[] args) {
			int[] arr = { 1,3,8,10,12 };
			int num = 3;
			System.out.println(minDistance(arr, num));
			System.out.println(minDis2(arr, num));

			int times = 100; // test time
			int len = 10000; // test array length
			int range = 2000; // every number in [0,range)
			int p = 50; // post office number max
			long time1 = 0; // method1 all run time
			long time2 = 0;// method2 all run time
			long start = 0;
			long end = 0;
			int res1 = 0;
			int res2 = 0;
			for (int i = 0; i != times; i++) {
				int office = (int) (Math.random() * p) + 1;
				arr = getSortedArray(len, range);
				start = System.currentTimeMillis();
				res1 = minDis1(arr, office);
				end = System.currentTimeMillis();
				time1 += end - start;
				start = System.currentTimeMillis();
				res2 = minDis2(arr, office);
				end = System.currentTimeMillis();
				time2 += end - start;

				if (res1 != res2) {
					printArray(arr);
					break;
				}
				if (i % 10 == 0) {
					System.out.print(". ");
				}
			}
			System.out.println();
			System.out.println("method1 all run time(ms): " + time1);
			System.out.println("method2 all run time(ms): " + time2);

		}
	}